package day2_linkedlist.leetcode;


/**
 * K个一组反转链表
 * @Author: yuisama
 * @Date: 2022/4/26 16:09
 * @Description:
 */
public class Num25_ReverseKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            if (tail == null) {
                // 剩余节点不够k了，不用翻转
                return head;
            }
            tail = tail.next;
        }
        ListNode newHead = reverseBetween(head,1,k);
        // 剩下节点的翻转交给子函数
        head.next = reverseKGroup(tail,k);
        return newHead;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        // 指向待翻转的前驱节点
        ListNode prev = dummyHead;
        // 指向第一个待翻转的节点
        ListNode cur = dummyHead.next;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
            cur = cur.next;
        }
        for (int i = 0; i < right - left; i++) {
            // 先把cur的next删除，再头插入prev的后面
            ListNode third = cur.next;
            cur.next = third.next;
            third.next = prev.next;
            prev.next = third;
        }
        return dummyHead.next;
    }
}
